{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Parallel Courses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSemesters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #并行课程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，表示编号从 <code>1</code> 到 <code>n</code> 的 <code>n</code> 门课程。另给你一个数组 <code>relations</code> ，其中 <code>relations[i] = [prevCourse<sub>i</sub>, nextCourse<sub>i</sub>]</code> ，表示课程 <code>prevCourse<sub>i</sub></code> 和课程 <code>nextCourse<sub>i</sub></code> 之间存在先修关系：课程 <code>prevCourse<sub>i</sub></code> 必须在 <code>nextCourse<sub>i</sub></code> 之前修读完成。</p>\n",
    "\n",
    "<p>在一个学期内，你可以学习 <strong>任意数量</strong> 的课程，但前提是你已经在上一学期修读完待学习课程的所有先修课程。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>请你返回学完全部课程所需的 <strong>最少</strong> 学期数。如果没有办法做到学完全部这些课程的话，就返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/24/course1graph.jpg\" style=\"width: 222px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, relations = [[1,3],[2,3]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>上图表示课程之间的关系图：\n",
    "在第一学期，可以修读课程 1 和 2 。\n",
    "在第二学期，可以修读课程 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/24/course2graph.jpg\" style=\"width: 222px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, relations = [[1,2],[2,3],[3,1]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>没有课程可以学习，因为它们互为先修课程。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 5000</code></li>\n",
    "\t<li><code>1 &lt;= relations.length &lt;= 5000</code></li>\n",
    "\t<li><code>relations[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= prevCourse<sub>i</sub>, nextCourse<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>prevCourse<sub>i</sub> != nextCourse<sub>i</sub></code></li>\n",
    "\t<li>所有 <code>[prevCourse<sub>i</sub>, nextCourse<sub>i</sub>]</code> <strong>互不相同</strong></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [parallel-courses](https://leetcode.cn/problems/parallel-courses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [parallel-courses](https://leetcode.cn/problems/parallel-courses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,3],[2,3]]', '3\\n[[1,2],[2,3],[3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "\n",
    "    \n",
    "        preClassCount = [0] * n\n",
    "        nextClass = [[] for i in range(n)]\n",
    "\n",
    "\n",
    "\n",
    "        for pre, nex in relations:\n",
    "            preClassCount[nex - 1] += 1\n",
    "            nextClass[pre - 1].append(nex - 1)\n",
    "\n",
    "        que = [i for i in range(n) if preClassCount[i] == 0]\n",
    "        res = 0\n",
    "        while que:\n",
    "            next_ = []\n",
    "            for cur in que:\n",
    "                for nex in nextClass[cur]:\n",
    "                    preClassCount[nex] -= 1\n",
    "                    if preClassCount[nex] == 0:\n",
    "                        next_.append(nex)\n",
    "            que = next_\n",
    "            res += 1\n",
    "        if sum(preClassCount) > 0: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        in_degress = [0]*n\n",
    "        for pre,nex in relations:\n",
    "            g[pre-1].append(nex-1)\n",
    "            in_degress[nex-1]+=1\n",
    "            \n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if in_degress[i]==0:\n",
    "                q.append(i)\n",
    "\n",
    "        level = 0\n",
    "        learned = 0\n",
    "        while q:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                learned+=1\n",
    "                for y in g[x]:\n",
    "                    in_degress[y]-=1\n",
    "                    if in_degress[y]==0:\n",
    "                        q.append(y)\n",
    "            level += 1\n",
    "\n",
    "        return level if learned==n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "\n",
    "    \n",
    "        preClassCount = [0] * n\n",
    "        nextClass = [[] for i in range(n)]\n",
    "\n",
    "\n",
    "\n",
    "        for pre, nex in relations:\n",
    "            preClassCount[nex - 1] += 1\n",
    "            nextClass[pre - 1].append(nex - 1)\n",
    "\n",
    "\n",
    "        que = [i for i in range(n) if preClassCount[i] == 0]\n",
    "        que = collections.deque(que)\n",
    "        res = 0\n",
    "        while que:\n",
    "            next_ = []\n",
    "            for cur in que:\n",
    "                for nex in nextClass[cur]:\n",
    "                    preClassCount[nex] -= 1\n",
    "                    if preClassCount[nex] == 0:\n",
    "                        next_.append(nex)\n",
    "            que = next_\n",
    "            res += 1\n",
    "        if sum(preClassCount) > 0: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        term = 0\n",
    "        # pretreatment\n",
    "        pre_class_cnt = [0]*n\n",
    "        next_class = [[] for i in range(n)]\n",
    "        for x,y in relations:\n",
    "            #入度\n",
    "            pre_class_cnt[y-1] +=1\n",
    "            #添加课程\n",
    "            next_class[x-1].append(y-1)\n",
    "        #初始化第一学期    \n",
    "        cur_semster = [i for i in range(n) if pre_class_cnt[i]==0 ]\n",
    "        while cur_semster:\n",
    "            next_semester = []\n",
    "            for cur in cur_semster:\n",
    "                for next in next_class[cur]:\n",
    "                    #入读--\n",
    "                    pre_class_cnt[next] -=1\n",
    "                    if pre_class_cnt[next]==0:\n",
    "                        next_semester.append(next)\n",
    "            \n",
    "            cur_semster = next_semester\n",
    "            term +=1\n",
    "        return -1 if sum(pre_class_cnt)>0 else term\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        indeg = [0] * (n+1)   \n",
    "        for e in relations:\n",
    "            g[e[0]].append(e[1])\n",
    "            indeg[e[1]] += 1 \n",
    "\n",
    "        q = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if indeg[i]==0:\n",
    "                q.append(i)\n",
    "                cnt += 1\n",
    "\n",
    "        res = 0\n",
    "        \n",
    "\n",
    "        while len(q)>0:\n",
    "            sz = len(q)\n",
    "            while sz>0:\n",
    "                sz -= 1\n",
    "                now = q[0]\n",
    "                q = q[1:]\n",
    "                cnt += 1\n",
    "                for x in g[now]:\n",
    "                    indeg[x] -= 1\n",
    "                    if indeg[x]==0:\n",
    "                        q.append(x)\n",
    "                        cnt += 1\n",
    "            res += 1\n",
    "\n",
    "        if cnt<n:\n",
    "            return -1\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        degree = [0] * n\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for (p, nx) in relations:\n",
    "            p, nx = p - 1, nx -1\n",
    "            degree[nx] += 1\n",
    "            adj[p].append(nx)\n",
    "        q = deque()\n",
    "        visited = 0\n",
    "        res = 0\n",
    "        for i, v in enumerate(degree):\n",
    "            if v == 0:\n",
    "                q.append(i)\n",
    "        while(q):\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                node = q.popleft()\n",
    "                visited += 1\n",
    "                for i in adj[node]:\n",
    "                    degree[i] -= 1\n",
    "                    if degree[i] == 0:\n",
    "                        q.append(i)\n",
    "            res += 1\n",
    "        return res if visited == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        ru=[0]*(n+1)\n",
    "        nx=[[] for i in range(n+1)]\n",
    "        for x,y in relations:\n",
    "            ru[y]+=1\n",
    "            nx[x].append(y)\n",
    "        q=[]\n",
    "        for i in range(1,n+1):\n",
    "            if ru[i]==0: q.append(i)\n",
    "     \n",
    "        i=1\n",
    "        sex=[0]*(n+1)\n",
    "        while(q):\n",
    "            nq=[]\n",
    "            for p in q:\n",
    "                sex[p]=-i\n",
    "                for pp in nx[p]:\n",
    "                    ru[pp]-=1\n",
    "                    if ru[pp]==0:\n",
    "                        nq.append(pp)\n",
    "            q=nq\n",
    "            i+=1\n",
    "        # print(ru)\n",
    "        # print(sex)\n",
    "        for i in sex[1:]:\n",
    "            if not i<0:\n",
    "                return -1\n",
    "\n",
    "        return -min(sex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        indeg = [0] * n\n",
    "        #这里需要将编号减1是为了下面方便入队列\n",
    "        for x, y in relations:\n",
    "            g[y - 1].append(x - 1)\n",
    "            indeg[x - 1] += 1\n",
    "        q = collections.deque(i for i, x in enumerate(indeg) if x == 0)\n",
    "        cnt = len(q)\n",
    "        res = []\n",
    "        depth = 0\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            res.append(i)\n",
    "            cnt -= 1\n",
    "            for j in g[i]:\n",
    "                indeg[j] -= 1\n",
    "                if indeg[j] == 0:\n",
    "                    q.append(j)\n",
    "            if not cnt:\n",
    "                depth += 1\n",
    "                cnt = len(q)\n",
    "        return depth if len(res) == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        indegree = [0] * (n + 1)\n",
    "        adj_nodes = {i: [] for i in range(n + 1)}\n",
    "        for a, b in relations:\n",
    "            indegree[b] += 1\n",
    "            adj_nodes[a].append(b)\n",
    "        \n",
    "        levels = 0\n",
    "        q = []\n",
    "        for i in range(1, n + 1):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "        count = n\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            levels += 1\n",
    "            for _ in range(l):\n",
    "                curr = q.pop(0)\n",
    "                count -= 1\n",
    "                for nxt in adj_nodes[curr]:\n",
    "                    indegree[nxt] -= 1\n",
    "                    if indegree[nxt] == 0:\n",
    "                        q.append(nxt)\n",
    "        return levels if count == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for info in relations:\n",
    "            edges[info[0]-1].append(info[1]-1)\n",
    "            indegree[info[1]-1] += 1\n",
    "        q = [u for u in range(n) if indegree[u] == 0]\n",
    "        res = 0\n",
    "        ans = list()\n",
    "        while q:\n",
    "            k = len(q)\n",
    "            res += 1\n",
    "            for _ in range(k):\n",
    "                u = q.pop(0)\n",
    "                ans.append(u)\n",
    "                for v in edges[u]:\n",
    "                    indegree[v] -= 1\n",
    "                    if indegree[v] == 0:\n",
    "                        q.append(v)\n",
    "        if len(ans) == n:\n",
    "            return res\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n+1)]\n",
    "        init = [True]*(n+1)\n",
    "        indegree = [0]*(n+1)\n",
    "        indegree[0] = -1\n",
    "\n",
    "\n",
    "        for relation in relations:\n",
    "            a, b = relation[0], relation[1]\n",
    "            graph[a].append(b)   \n",
    "            indegree[b] += 1\n",
    "            \n",
    "\n",
    "        # print(graph)\n",
    "\n",
    "        q = collections.deque([i for i in range(1,n+1) if indegree[i] == 0])\n",
    "        # if not q:\n",
    "        #     return -1\n",
    "\n",
    "        # visited = [False]*(n+1)\n",
    "        # selected = [False]*(n+1)\n",
    "        # 如果在遍历过程中发现下一个指向的点是之前访问过的 报错\n",
    "        res = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                c = q.popleft()\n",
    "                # selected[c] = True\n",
    "                for nxt in graph[c]:\n",
    "                    # if indegree[nxt] < 0:\n",
    "                    #     print(nxt)\n",
    "                    #     return -1\n",
    "                    indegree[nxt] -= 1\n",
    "                    if indegree[nxt] == 0:\n",
    "                        q.append(nxt)\n",
    "                    # if selected[nxt]:\n",
    "                    #     # print(nxt)\n",
    "                    #     return -1\n",
    "                    \n",
    "                    # if not visited[nxt]:\n",
    "                    #     visited[nxt] = True\n",
    "                    #     q.append(nxt) \n",
    "            res += 1\n",
    "        for i in range(1, n+1):\n",
    "            if indegree[i] != 0:\n",
    "                return -1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "        # visited = [False]*(n+1)\n",
    "        # # 如果在遍历过程中发现下一个指向的点是之前访问过的 报错\n",
    "        # res = 1\n",
    "        # while q:\n",
    "        #     size = len(q)\n",
    "        #     for i in range(size):\n",
    "        #         c = q.popleft()\n",
    "        #         for nxt in graph[c]:\n",
    "        #             if visited[nxt]:\n",
    "        #                 return -1\n",
    "        #             visited[nxt] = True\n",
    "        #             q.append(nxt) \n",
    "        #     res += 1\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "        # res = 1\n",
    "        # while q:\n",
    "        #     c = q.popleft()\n",
    "        #     for nxt in graph[c]:\n",
    "        #         if visited[nxt]:\n",
    "        #             return -1\n",
    "        #         q.append(nxt) \n",
    "        #     res += 1\n",
    "        # return res\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        father = defaultdict(list)\n",
    "        for i, j in relations:\n",
    "            indegree[j] += 1\n",
    "            father[i].append(j)\n",
    "        q = [x for x in range(1, n + 1) if x not in indegree]\n",
    "        level = 0\n",
    "        tmp_list = []\n",
    "        while q:\n",
    "            t = q.pop()\n",
    "            n -= 1\n",
    "            for i in father.get(t, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    tmp_list.append(i)\n",
    "            if not q:\n",
    "                q.extend(tmp_list)\n",
    "                level += 1\n",
    "                tmp_list.clear()\n",
    "\n",
    "        return level if n ==0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        indegree = [0]*(n)\n",
    "        d = defaultdict(list)\n",
    "        for a,b in relations:\n",
    "            d[a-1].append(b-1)\n",
    "            indegree[b-1]+=1\n",
    "        visit = 0\n",
    "        res = 0\n",
    "        q = deque([node for node in range(n) if indegree[node]==0])\n",
    "        while q:\n",
    "            res+=1\n",
    "            next_q = deque()\n",
    "            while q:\n",
    "                tmp = q.popleft()\n",
    "                visit+=1\n",
    "                for node in d[tmp]:\n",
    "                    indegree[node]-=1\n",
    "                    if indegree[node]==0:\n",
    "                        next_q.append(node)\n",
    "            q = next_q\n",
    "        return res if visit==n else -1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        parent = defaultdict(list)\n",
    "\n",
    "        for i, j in relations:\n",
    "            indegree[j] += 1\n",
    "            parent[i].append(j)\n",
    "        # print(\"ind:\", indegree)\n",
    "        zero = [x for x in range(1, n + 1) if x not in indegree]\n",
    "        # print(zero)\n",
    "        if not zero:\n",
    "            return -1\n",
    "        res = []\n",
    "        ans = 0\n",
    "        while zero:\n",
    "            # print(\"zero:\", zero)\n",
    "            tmp = zero.pop()\n",
    "            n -= 1\n",
    "            for i in parent.get(tmp, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    res.append(i)\n",
    "            if not zero:\n",
    "                ans += 1\n",
    "                zero.extend(res)\n",
    "                res.clear()\n",
    "        print(n)\n",
    "        if n == 0:\n",
    "            return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(1, N + 1)}\n",
    "        in_count = {i: 0 for i in range(1, N + 1)}\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "            in_count[end_node] += 1\n",
    "        \n",
    "        queue = []\n",
    "        for node in graph:\n",
    "            if in_count[node] == 0:\n",
    "                queue.append(node)\n",
    "        \n",
    "        step = 0\n",
    "        studied_count = 0\n",
    "        while queue:\n",
    "            step += 1\n",
    "            next_queue = []\n",
    "            for node in queue:\n",
    "                studied_count += 1\n",
    "                end_nodes = graph[node]\n",
    "                for end_node in end_nodes:\n",
    "                    in_count[end_node] -= 1\n",
    "                    if in_count[end_node] == 0:\n",
    "                        next_queue.append(end_node)\n",
    "            queue = next_queue\n",
    "        return step if studied_count == N else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(1, N + 1)}\n",
    "        in_count = {i: 0 for i in range(1, N + 1)}  # 或者入度\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "            in_count[end_node] += 1\n",
    "\n",
    "        queue = []\n",
    "        # 我们使用 list 因为我们\n",
    "        # 在这份代码中不会弹出前面的元素\n",
    "        for node in graph:\n",
    "            if in_count[node] == 0:\n",
    "                queue.append(node)\n",
    "\n",
    "        step = 0\n",
    "        studied_count = 0\n",
    "        # 开始使用BFS学习\n",
    "        while queue:\n",
    "            # 开始一个新学期\n",
    "            step += 1\n",
    "            next_queue = []\n",
    "            for node in queue:\n",
    "                studied_count += 1\n",
    "                end_nodes = graph[node]\n",
    "                for end_node in end_nodes:\n",
    "                    in_count[end_node] -= 1\n",
    "                    # 如果所有先修课程都已经学习\n",
    "                    if in_count[end_node] == 0:\n",
    "                        next_queue.append(end_node)\n",
    "            queue = next_queue\n",
    "\n",
    "        return step if studied_count == N else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        # directed graph & indegree\n",
    "        g = defaultdict(list)\n",
    "        indeg = [0] * n\n",
    "        \n",
    "        for pre, lat in relations:\n",
    "            g[pre-1].append(lat-1) \n",
    "            indeg[lat-1] += 1\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        \n",
    "        # check cyclic \n",
    "        \n",
    "        def cyclic(g):\n",
    "            return \n",
    "\n",
    "        if cyclic(g):\n",
    "            return -1\n",
    "\n",
    "\n",
    "        # add all first \n",
    "\n",
    "        time2finish = [0]*n\n",
    "        q = deque()\n",
    "        for i, key in enumerate(g.keys()):\n",
    "            if indeg[key] == 0:\n",
    "                q.append(key)\n",
    "                time2finish[key] = 1\n",
    "\n",
    "\n",
    "\n",
    "        # topo sort\n",
    "\n",
    "        res = 0\n",
    "        num_visited = 0\n",
    "        steps = 0\n",
    "        while q: # we consider all nodes\n",
    "            for _ in range(len(q)):\n",
    "                cur_node = q.popleft()\n",
    "                num_visited += 1\n",
    "                for child in g[cur_node]:\n",
    "\n",
    "                    indeg[child] -= 1\n",
    "                    time2finish[child] = max(time2finish[child], time2finish[cur_node]+1)\n",
    "                    res = max(res, time2finish[child])\n",
    "                    if indeg[child] == 0:\n",
    "                        q.append(child)\n",
    "            steps += 1\n",
    "        print(res, steps)\n",
    "        return steps if num_visited == len(g) else -1\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        ad=collections.defaultdict(list)\n",
    "        ind={i:0 for  i in range(1,n+1)}\n",
    "        for pre,nex in relations:\n",
    "            ad[pre].append(nex)\n",
    "            ind[nex]+=1\n",
    "        stack=collections.deque()\n",
    "        nexstack=collections.deque()\n",
    "        cnt=1\n",
    "        for x in ind:\n",
    "            if ind[x]==0:\n",
    "                stack.append(x)\n",
    "        vis=[]\n",
    "        while stack:\n",
    "            cur=stack.popleft()\n",
    "            vis.append(cur)\n",
    "            for nex in ad[cur]:\n",
    "                ind[nex]-=1\n",
    "                if ind[nex]==0:\n",
    "                    nexstack.append(nex)\n",
    "            if not stack and nexstack:\n",
    "                cnt+=1\n",
    "                stack=nexstack\n",
    "                nexstack=collections.deque()\n",
    "\n",
    "        if len(vis)!=n:\n",
    "            return -1\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(1, N + 1)}\n",
    "        in_count = {i: 0 for i in range(1, N + 1)}  # 或者入度\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "            in_count[end_node] += 1\n",
    "\n",
    "        queue = []\n",
    "        # 我们使用 list 因为我们\n",
    "        # 在这份代码中不会弹出前面的元素\n",
    "        for node in graph:\n",
    "            if in_count[node] == 0:\n",
    "                queue.append(node)\n",
    "\n",
    "        step = 0\n",
    "        studied_count = 0\n",
    "        # 开始使用BFS学习\n",
    "        while queue:\n",
    "            # 开始一个新学期\n",
    "            step += 1\n",
    "            next_queue = []\n",
    "            for node in queue:\n",
    "                studied_count += 1\n",
    "                end_nodes = graph[node]\n",
    "                for end_node in end_nodes:\n",
    "                    in_count[end_node] -= 1\n",
    "                    # 如果所有先修课程都已经学习\n",
    "                    if in_count[end_node] == 0:\n",
    "                        next_queue.append(end_node)\n",
    "            queue = next_queue\n",
    "\n",
    "        return step if studied_count == N else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(1, n + 1)}\n",
    "        in_degree = {i: 0 for i in range(1, n + 1)}\n",
    "\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "            in_degree[end_node] += 1\n",
    "\n",
    "        queue = []\n",
    "        for node in graph:\n",
    "            if in_degree[node] == 0:\n",
    "                queue.append(node)\n",
    "\n",
    "        term, complete_count = 0, 0\n",
    "\n",
    "        while queue:\n",
    "            term += 1\n",
    "            next_queue = []\n",
    "            for node in queue:\n",
    "                complete_count += 1\n",
    "                end_nodes = graph[node]\n",
    "                for end_node in end_nodes:\n",
    "                    in_degree[end_node] -= 1\n",
    "                    if in_degree[end_node] == 0:\n",
    "                        next_queue.append(end_node)\n",
    "            queue = next_queue\n",
    "\n",
    "        return term if complete_count == n else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        pres = [[] for _ in range(n+1)]\n",
    "        indegree = [0]*(n+1)\n",
    "        for pre, nxt in relations:\n",
    "            pres[pre].append(nxt)\n",
    "            indegree[nxt] += 1\n",
    "        from collections import deque\n",
    "        dq = deque([])\n",
    "        visited = set()\n",
    "        for i in range(1,n+1):\n",
    "            if indegree[i] == 0:\n",
    "                dq.append(i)\n",
    "                visited.add(i)\n",
    "        if not dq: return -1\n",
    "\n",
    "        semester = 0\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            for i in range(size):\n",
    "                cur = dq.popleft()\n",
    "                for nxt in pres[cur]:\n",
    "                    indegree[nxt] -= 1\n",
    "                    if indegree[nxt] == 0 and nxt not in visited:\n",
    "                        visited.add(nxt)\n",
    "                        dq.append(nxt)\n",
    "            semester += 1\n",
    "        \n",
    "        if len(visited) != n: return -1\n",
    "        return semester\n",
    "                        \n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        \"\"\" Classic TopSort \"\"\"\n",
    "\n",
    "        # UniG\n",
    "        G = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        for u, v in relations:\n",
    "            G[u].append(v)\n",
    "            indeg[v] += 1 \n",
    "        \n",
    "        queue = collections.deque([(i,1) for i in range(n) if i not in indeg])\n",
    "\n",
    "        ans = 1\n",
    "        while queue:\n",
    "            curr_u, curr_level = queue.popleft()\n",
    "            for v in G[curr_u]:\n",
    "                indeg[v] -= 1 \n",
    "                if not indeg[v]:\n",
    "                    ans = curr_level+1\n",
    "                    queue.append((v,curr_level+1))\n",
    "\n",
    "\n",
    "        return ans if not sum(list(indeg.values())) else -1 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        indeg = [0]*(n+1)\n",
    "        g = [set() for _ in range(n+1)]\n",
    "        for a,b in relations:\n",
    "            # print(a,b,n)\n",
    "            indeg[b]+=1\n",
    "            g[a].add(b)\n",
    "\n",
    "        zq = deque(filter(lambda i:indeg[i]==0,range(1,n+1)))\n",
    "        cnt =0 \n",
    "        level = 0\n",
    "        # print(g[1])\n",
    "        while zq:\n",
    "            level+=1\n",
    "            # print(zq)\n",
    "            for _ in range(len(zq)):\n",
    "                cur = zq.popleft()\n",
    "                cnt+=1\n",
    "                # print(cur,g[cur])\n",
    "                for c in g[cur]:\n",
    "                    indeg[c]-=1\n",
    "                    if indeg[c]==0:\n",
    "                        zq.append(c)\n",
    "                \n",
    "        return level if cnt==n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        dic = defaultdict(set)\n",
    "        ans = [0]*n\n",
    "        for f,t in relations:\n",
    "            dic[f].add(t)\n",
    "            ans[t-1] += 1\n",
    "        queue = [i+1 for i in range(n) if ans[i] == 0]\n",
    "        #print(ans,queue)\n",
    "        res,cnt = 0,0\n",
    "        while queue:\n",
    "            queue2 = []\n",
    "            for key in queue:\n",
    "                cnt += 1\n",
    "                for u in dic[key]:\n",
    "                    ans[u-1] -= 1\n",
    "                    if ans[u-1] == 0:\n",
    "                        queue2.append(u)\n",
    "            res += 1\n",
    "            queue = queue2\n",
    "        #print(res,cnt)\n",
    "        return res if cnt == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        cnt = n\n",
    "        c = [{} for _ in range(n)]\n",
    "        for r in relations:\n",
    "            c[r[0]-1][r[1]-1] = 1\n",
    "\n",
    "        ans = 0\n",
    "        while True and cnt > 0:\n",
    "            todo = []\n",
    "            for i in range(n):\n",
    "                if c[i] == 1: continue\n",
    "                if c[i] == {}:\n",
    "                    todo.append(i)\n",
    "                    cnt -=1\n",
    "            if len(todo) == 0: break\n",
    "            for todoc in todo:\n",
    "                for i in range(n):\n",
    "                    if c[i] !=1 and todoc in c[i]:\n",
    "                        del c[i][todoc]\n",
    "                c[todoc] = 1\n",
    "            ans +=1\n",
    "        return ans if cnt == 0 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        return self.answer_1(n, relations)\n",
    "\n",
    "    def answer_1(self, n, relations):\n",
    "        graph = collections.defaultdict(list)\n",
    "        graph = {i: [] for i in range(1, n + 1)}\n",
    "\n",
    "        for in_, out_ in relations:\n",
    "            graph[in_].append(out_)\n",
    "\n",
    "        for node in graph:\n",
    "            if self._check_cycle(node, graph):\n",
    "                return -1\n",
    "\n",
    "        return max([self._get_max_length(i, graph) for i in graph])\n",
    "\n",
    "    def _get_max_length(self, node, graph, flag=None):\n",
    "        if flag is None:\n",
    "            flag = {}\n",
    "\n",
    "        if node in flag:\n",
    "            return flag[node]\n",
    "\n",
    "        max_length = 1\n",
    "        for out_node in graph[node]:\n",
    "            length = self._get_max_length(out_node, graph, flag)\n",
    "            max_length = max(max_length, length + 1)\n",
    "        flag[node] = max_length\n",
    "        return max_length\n",
    "\n",
    "    def _check_cycle(self, node, graph, flag=None):\n",
    "        if flag is None:\n",
    "            flag = {}\n",
    "\n",
    "        if node in flag:\n",
    "            return flag[node]\n",
    "\n",
    "        flag[node] = True\n",
    "  \n",
    "        for out_node in graph[node]:\n",
    "            if self._check_cycle(out_node, graph, flag):\n",
    "                return True\n",
    "        flag[node] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        d = [0] * (n + 1)\n",
    "        for u, v in relations:\n",
    "            g[u].append(v)\n",
    "            d[v] += 1\n",
    "        q = [i for i, x in enumerate(d) if x == 0 and i != 0]\n",
    "        # print(f'{q}')\n",
    "        ans = 0\n",
    "        s = set()\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            ans += 1\n",
    "            for x in tmp:\n",
    "                s.add(x)\n",
    "                for y in g[x]:\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 0:\n",
    "                        q.append(y)\n",
    "        return ans if ans != 0 and len(s) == n else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for relation in relations:\n",
    "            edges[relation[0]-1].append(relation[1]-1)\n",
    "            indegree[relation[1]-1] += 1\n",
    "        \n",
    "        q = [(u, 0) for u in range(n) if indegree[u] == 0]\n",
    "        res = list()\n",
    "        while q:\n",
    "            \n",
    "            u, depth = q.pop(0)\n",
    "            res.append((u, depth))\n",
    "            for v in edges[u]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    q.append((v, depth+1))\n",
    "        if len(res) != n:\n",
    "            return -1\n",
    "        return res[-1][1] + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        # DAG问题，准备两个字典即可\n",
    "        pre = {i: set() for i in range(1, N + 1)} # 每个都要有计算前项的\n",
    "        nxt = collections.defaultdict(set)      # 不一定每个都要有计算后项的\n",
    "        for u, v in relations: \n",
    "            nxt[u].add(v)\n",
    "            pre[v].add(u)\n",
    "        \n",
    "        queue = collections.deque([u for u in pre if not pre[u]])\n",
    "        N -= len(queue) # 整体计数器\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                u = queue.popleft()\n",
    "                for v in nxt[u]:\n",
    "                    pre[v].remove(u)\n",
    "                    if len(pre[v]) == 0:\n",
    "                        queue.append(v)\n",
    "                        N -= 1\n",
    "            ans += 1\n",
    "        return ans if N == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        indegree = [0] * (n + 1)\n",
    "        for pre, nxt in relations:\n",
    "            graph[pre].append(nxt)\n",
    "            indegree[nxt] += 1\n",
    "        \n",
    "        queue = []\n",
    "        for i in range(1, n + 1):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            ans += 1\n",
    "            size = len(queue)\n",
    "            while size > 0:\n",
    "                u = queue.pop(0)\n",
    "                visited.add(u)\n",
    "                for v in graph[u]:\n",
    "                    indegree[v] -= 1\n",
    "                    if indegree[v] == 0:\n",
    "                        queue.append(v)\n",
    "                size -= 1\n",
    "        return ans if len(visited) == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)  # 建立图的邻接表\n",
    "        indegree = [0] * (n + 1)  # 建立图顶点的入度表\n",
    "        for pre, nxt in relations:\n",
    "            graph[pre].append(nxt)\n",
    "            indegree[nxt] += 1\n",
    "        \n",
    "        queue = []\n",
    "        for i in range(1, n + 1):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            ans += 1\n",
    "            size = len(queue)\n",
    "            while size > 0:\n",
    "                u = queue.pop(0)\n",
    "                visited.add(u)\n",
    "                for v in graph[u]:\n",
    "                    indegree[v] -= 1\n",
    "                    if indegree[v] == 0:\n",
    "                        queue.append(v)\n",
    "                size -= 1\n",
    "        return ans if len(visited) == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        adj = defaultdict(list)\n",
    "        indegree = [0] * (n+1)\n",
    "        for a, b in relations:\n",
    "            adj[a].append(b)\n",
    "            indegree[b] += 1\n",
    "        \n",
    "        q = deque([])\n",
    "        for i in range(1, n + 1):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "        \n",
    "        # print(q)\n",
    "        s = sum(indegree)\n",
    "        visited = set(q)\n",
    "        k = 0\n",
    "        while q:\n",
    "            nn = len(q)\n",
    "            while nn > 0:\n",
    "                x = q.popleft()\n",
    "                for nx in adj[x]:\n",
    "                    # print(nx)\n",
    "                    if nx in visited:\n",
    "                        return -1\n",
    "                    indegree[nx] -= 1\n",
    "                    if indegree[nx] == 0:\n",
    "                        q.append(nx)\n",
    "                        visited.add(nx)\n",
    "                nn -= 1\n",
    "            k += 1\n",
    "        if sum(indegree) > 0:\n",
    "            return -1\n",
    "        return k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        for x in range(1,n+1):\n",
    "            graph[x] = []\n",
    "            indegree[x] = 0\n",
    "        for x, y in relations:\n",
    "            graph[x].append(y)\n",
    "            indegree[y] += 1\n",
    "        queue = []\n",
    "        for x in indegree:\n",
    "            if indegree[x] == 0:\n",
    "                queue.append(x)\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            nxt = []\n",
    "            while queue:\n",
    "                x = queue.pop()\n",
    "                visited.add(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegree[nei] -= 1\n",
    "                    if indegree[nei] == 0:\n",
    "                        nxt.append(nei)\n",
    "            queue = nxt\n",
    "            res += 1\n",
    "        if len(visited) == n:\n",
    "            return res\n",
    "        return -1\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        indeg, graph = {}, {}\n",
    "        for i in range(1, n + 1):\n",
    "            indeg[i] = 0\n",
    "            graph[i] = []\n",
    "        for prev, next in relations:\n",
    "            indeg[next] += 1\n",
    "            graph[prev].append(next)\n",
    "        queue = deque()\n",
    "        for node, deg in indeg.items():\n",
    "            if deg == 0:\n",
    "                queue.append(node)\n",
    "        \n",
    "        vis = set(queue)\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                for adj in graph[node]:\n",
    "                    indeg[adj] -= 1\n",
    "                    if adj not in vis and indeg[adj] == 0:\n",
    "                        queue.append(adj)\n",
    "                        vis.add(adj)\n",
    "            step += 1\n",
    "        return step if len(vis) == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        g = defaultdict(set)\n",
    "        for i, j in relations:\n",
    "            g[i].add(j)\n",
    "            d[j] += 1\n",
    "\n",
    "        \n",
    "        q = [i for i in range(1, n + 1) if d[i] == 0]\n",
    "        t = 0\n",
    "        c = 0\n",
    "\n",
    "        while q:\n",
    "            nq = []\n",
    "            t += 1\n",
    "            c += len(q)\n",
    "            for i in range(len(q)):\n",
    "                for j in g[q[i]]:\n",
    "                    d[j] -= 1\n",
    "                    if d[j] == 0:\n",
    "                        nq.append(j)\n",
    "            q = nq\n",
    "        \n",
    "        if c == n:\n",
    "            return t\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class GNode():\n",
    "    def __init__(self, value, in_degree=None, out_degree=None):\n",
    "        self.value = value\n",
    "        self.in_degree = in_degree\n",
    "        self.out_degree = out_degree\n",
    "        self.nexts = []\n",
    "        self.edges = []\n",
    "#     def set_degrees(self):\n",
    "#         self.in_degree = self.out_degree = len(self.nexts)\n",
    "    def __repr__(self):\n",
    "        return f\"GNode {self.value}.\"\n",
    "        \n",
    "class Edge():\n",
    "    def __init__(self, weight=1, from_node=None, to_node=None):\n",
    "        self.weight=weight\n",
    "        self.from_node=from_node\n",
    "        self.to_node=to_node\n",
    "    def __lt__(self,other):\n",
    "        return self.weight < other.weight\n",
    "    def __repr__(self):\n",
    "        return f\"{self.from_node} --{self.weight}--> {self.to_node}\"\n",
    "        \n",
    "class Graph():\n",
    "    def __init__(self,):\n",
    "        self.nodes=[]\n",
    "        self.edges=[]\n",
    "    def __repr__(self):\n",
    "        return f\"Graph has {len(self.nodes)} nodes, {len(self.edges)} edges.\"\n",
    "\n",
    "def make_Graph_from_sp(lines):\n",
    "    nodes = {} # key:nodevalue, value:Node\n",
    "    edges = []\n",
    "    for line in lines:\n",
    "        node1_val, node2_val = line\n",
    "        weight = 1\n",
    "        node1_val, node2_val = node1_val, node2_val\n",
    "        nodes.setdefault(node1_val, GNode(node1_val))\n",
    "        nodes.setdefault(node2_val, GNode(node2_val))\n",
    "        edges.append(Edge(weight, nodes[node1_val], nodes[node2_val]))\n",
    "\n",
    "    # 统计出度入度(拓扑排序需要). 删去可大幅加速. \n",
    "    for val, node in nodes.items():\n",
    "        # 该点指出的点. \n",
    "        node_nexts = [e.to_node for e in edges if e.from_node==node]\n",
    "        # 哪些点指向该点\n",
    "        node_tothis = [e.from_node for e in edges if e.to_node==node]\n",
    "        \n",
    "        node.in_degree = len(node_tothis)\n",
    "        node.out_degree = len(node_nexts)\n",
    "        node.nexts = node_nexts\n",
    "        node.edges = node_nexts + node_tothis\n",
    "\n",
    "    graph = Graph()\n",
    "    graph.nodes = [n for i,n in nodes.items()]\n",
    "    graph.edges = edges\n",
    "    return graph\n",
    "\n",
    "from queue import Queue\n",
    "# 修改为广度优先遍历\n",
    "class TopologySort():\n",
    "    def sort(self, graph):\n",
    "        inMap = {}\n",
    "        zeroInQueue = Queue()\n",
    "        for n in graph.nodes:\n",
    "            inMap[n] = n.in_degree\n",
    "            if n.in_degree == 0: zeroInQueue.put(n)\n",
    "        \n",
    "        # res_list = []\n",
    "        zero_num = 0\n",
    "        while not zeroInQueue.empty():\n",
    "            for _ in range(zeroInQueue.qsize()):\n",
    "                curr_node = zeroInQueue.get()\n",
    "                # res_list.append(curr_node)\n",
    "                for n in curr_node.nexts:\n",
    "                    inMap[n] -= 1\n",
    "                    if inMap[n] == 0: zeroInQueue.put(n)\n",
    "            zero_num += 1\n",
    "        non_zero_num = sum([1 for k,v in inMap.items() if v!=0])\n",
    "        return non_zero_num, zero_num\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = make_Graph_from_sp(relations)\n",
    "        non_zero_num, zero_num = TopologySort().sort(graph)\n",
    "        if non_zero_num != 0 : return -1\n",
    "        return zero_num\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## -----------官方---------------- ##\n",
    "# class Solution:\n",
    "#     def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "#         pre_class_cnt = [0] * N\n",
    "#         next_classes = [[] for i in range(N)]\n",
    "#         for a, b in relations:\n",
    "#             pre_class_cnt[b - 1] += 1\n",
    "#             next_classes[a - 1].append(b - 1)\n",
    "#         learn = [i for i in range(N) if pre_class_cnt[i] == 0]\n",
    "#         term = 0\n",
    "#         while learn:\n",
    "#             next_semester = []\n",
    "#             for cur_class in learn:\n",
    "#                 for next_class in next_classes[cur_class]:\n",
    "#                     pre_class_cnt[next_class] -= 1\n",
    "#                     if pre_class_cnt[next_class] == 0:\n",
    "#                         next_semester.append(next_class)\n",
    "#             learn = next_semester\n",
    "#             term += 1\n",
    "#         if sum(pre_class_cnt) > 0:\n",
    "#             return -1\n",
    "#         return term\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        indeg, graph = {}, {}\n",
    "        for i in range(1, n + 1):\n",
    "            indeg[i] = 0\n",
    "            graph[i] = []\n",
    "        for prev, next in relations:\n",
    "            indeg[next] += 1\n",
    "            graph[prev].append(next)\n",
    "        queue = deque()\n",
    "        for node, deg in indeg.items():\n",
    "            if deg == 0:\n",
    "                queue.append(node)\n",
    "        vis = set(queue)\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                for adj in graph[node]:\n",
    "                    indeg[adj] -= 1\n",
    "                    if adj not in vis and indeg[adj] == 0:\n",
    "                        queue.append(adj)\n",
    "                        vis.add(adj)\n",
    "            step += 1\n",
    "        return step if len(vis) == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        pres=[[] for _ in range(n)]\n",
    "        serp=[[] for _ in range(n)]\n",
    "        for relation in relations:\n",
    "            pres[relation[0]-1].append(relation[1]-1)\n",
    "            serp[relation[1]-1].append(relation[0]-1)\n",
    "        exitDeg=[len(pres[i]) for i in range(n)]\n",
    "        queue=list()\n",
    "        courses=list()\n",
    "        for i in range(n):\n",
    "            if exitDeg[i]==0: queue.append([i,1])\n",
    "        while queue:\n",
    "            head=queue.pop(0)\n",
    "            courses.append(head)\n",
    "            course=head[0]\n",
    "            semester=head[1]\n",
    "            for cours in serp[course]:\n",
    "                exitDeg[cours]-=1\n",
    "                if exitDeg[cours]==0: queue.append([cours, semester+1])\n",
    "        #print(courses)\n",
    "        return courses[-1][1] if len(courses)==n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        record=[0 for i in range(n+1)]\n",
    "        valid=True\n",
    "        graph=[[]for i in range(n+1)]\n",
    "        res=[1 for i in range(n+1)]\n",
    "        for i,j in relations:\n",
    "            graph[j].append(i)\n",
    "\n",
    "        \n",
    "        def dfs(cur,depth):\n",
    "            nonlocal valid\n",
    "            nonlocal maxx\n",
    "            record[cur]=1\n",
    "            for fa in graph[cur]:\n",
    "                if record[fa]==0:\n",
    "                    maxx=max(maxx,depth+1)\n",
    "                    dfs(fa,depth+1)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif record[fa]==1:\n",
    "                    valid=False\n",
    "                    return\n",
    "                elif record[fa]==2:\n",
    "                    maxx=max(maxx,res[fa]+1)\n",
    "            record[cur]=2\n",
    "            res[cur]=maxx\n",
    "            return\n",
    "        for i in range(1,n+1):\n",
    "            if record[i]==0:\n",
    "                maxx=1\n",
    "                dfs(i,1)\n",
    "        if not valid:\n",
    "            return -1\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "            \n",
    "            UNVISITED, VISITING, VISITED = 0, 1, 2\n",
    "            status = [UNVISITED] * ( n + 1)\n",
    "            adjacency_list = [[] for _ in range(n + 1)]\n",
    "            has_loop = False\n",
    "            depth = [1] * (n + 1) # 记录每个节点最大call stack深度\n",
    "             \n",
    "            def dfs(node):\n",
    "                nonlocal has_loop\n",
    "                if has_loop: return\n",
    "                if status[node] == VISITING:\n",
    "                # 回到正在搜索的节点说明有环\n",
    "                    has_loop = True\n",
    "                    return \n",
    "                if status[node] == VISITED:\n",
    "                # 遇到已经搜索完成的节点可以返回了，该节点已在栈中，不返回的话就死循环了\n",
    "                    return  \n",
    "                # 只对没有访问过的节点开始搜索\n",
    "                status[node] = VISITING # 在入栈前先标记\n",
    "                for neighbor in adjacency_list[node]:\n",
    "                    dfs(neighbor)\n",
    "                    depth[node] = max(depth[node], depth[neighbor] + 1)\n",
    "                status[node] = VISITED # 出栈返回后标记已访问\n",
    "                return \n",
    "            \n",
    "            for course, prerequisite in relations:\n",
    "                adjacency_list[prerequisite].append(course)\n",
    "\n",
    "            for course in range(1, n + 1):\n",
    "                if status[course] == UNVISITED:\n",
    "                    dfs(course)\n",
    "                    if has_loop: return -1\n",
    "                    \n",
    "            return max(depth) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        learned = set()\n",
    "        not_learned = set(range(1, n+1))\n",
    "        remain_not_learn = set()\n",
    "        ans = 0\n",
    "        course_prev_dict = defaultdict(set)\n",
    "\n",
    "        for prev, course in relations:\n",
    "            course_prev_dict[course].add(prev)\n",
    "        \n",
    "        while remain_not_learn != not_learned:\n",
    "            \n",
    "            ans += 1\n",
    "            cur_learn = set()\n",
    "            for course in not_learned - learned:\n",
    "                prev_couses = course_prev_dict.get(course, [])\n",
    "\n",
    "                able_learned = True\n",
    "                for prev_couse in prev_couses:\n",
    "                    if prev_couse not in learned:\n",
    "                        able_learned = False\n",
    "                if able_learned:\n",
    "                    cur_learn.add(course)\n",
    "                else:\n",
    "                    remain_not_learn.add(course)\n",
    "            \n",
    "            if remain_not_learn == not_learned:\n",
    "                return -1\n",
    "\n",
    "            learned = learned | cur_learn\n",
    "            not_learned = remain_not_learn\n",
    "            remain_not_learn = set()\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        vis = [0] * (n + 1)\n",
    "        depth = [1] * (n + 1)\n",
    "        for x, y in relations:\n",
    "            g[y].append(x)\n",
    "        def dfs(u: int) -> bool:\n",
    "            if vis[u] == 1:\n",
    "                return False\n",
    "            if vis[u] == -1:\n",
    "                return True\n",
    "            vis[u] = 1\n",
    "            for v in g[u]:\n",
    "                if not dfs(v):\n",
    "                    return False\n",
    "                depth[u] = max(depth[u], depth[v] + 1)\n",
    "            vis[u] = -1\n",
    "            return True\n",
    "        ans = 0\n",
    "        for i in range(n + 1):\n",
    "            if not dfs(i):\n",
    "                return -1\n",
    "            else:\n",
    "                ans = max(ans, depth[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        # 记录每个节点的入度，每学期学习所有入度为0的课程\n",
    "        # lessons 表示尚未学习的课程\n",
    "        lessons = {i+1 for i in range(n)}\n",
    "        # pre 和 post 分别表明这节课的前置和后置课程\n",
    "        pre = {i+1:set() for i in range(n)}\n",
    "        post = {i+1:set() for i in range(n)}\n",
    "        for i,j in relations:\n",
    "            pre[j].add(i)\n",
    "            post[i].add(j)\n",
    "        rv = 0\n",
    "        while lessons:\n",
    "            # 检查所有可学习的课程\n",
    "            learn = set() \n",
    "            for i in lessons:\n",
    "                if not pre[i]:\n",
    "                    learn.add(i)\n",
    "            # 啥也学不了\n",
    "            if not learn:\n",
    "                return -1 \n",
    "            # 进行本学期课程的学习\n",
    "            rv += 1\n",
    "            for i in learn:\n",
    "                lessons.remove(i)\n",
    "                for j in post[i]:\n",
    "                    pre[j].remove(i)\n",
    "        return rv "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        # DFS, check cycle while looking for minimum number of semesters\n",
    "        # use state: 0 for NOT VISITED, 1 for VISITING, 2 for VISITED\n",
    "\n",
    "        dist = [0]*(n+1)\n",
    "        def dfs(i):\n",
    "            # modify dist and visited of each node in the path, return false if cycle exists, else true\n",
    "            visited[i] = VISITING\n",
    "            if i not in adj_list:\n",
    "                dist[i] = 1\n",
    "            else:\n",
    "                for neighbor in adj_list[i]:\n",
    "                    if visited[neighbor] == 2:\n",
    "                        dist[i] = max(dist[i],dist[neighbor]+1)\n",
    "                    elif visited[neighbor] == 1:\n",
    "                        return False \n",
    "                    else:\n",
    "                        temp = dfs(neighbor)\n",
    "                        if not temp:\n",
    "                            return False\n",
    "                        else:\n",
    "                            dist[i] = max(dist[i],dist[neighbor]+1)\n",
    "            visited[i] = 2\n",
    "            # print(i,dist)\n",
    "            return True\n",
    "\n",
    "\n",
    "        # create adjacency list\n",
    "        adj_list = {}\n",
    "        for x,y in relations:\n",
    "            if x not in adj_list:\n",
    "                adj_list[x] = [y]\n",
    "            else:\n",
    "                adj_list[x].append(y)\n",
    "\n",
    "        # print(adj_list)\n",
    "        NOT_VISITED, VISITING, VISITED = 0,1,2\n",
    "        visited = [0]*(n+1)\n",
    "\n",
    "        # run DFS on each course\n",
    "        for i in range(1,n+1):\n",
    "            if visited[i] == 0:\n",
    "                temp = dfs(i)\n",
    "                if not temp:\n",
    "                    return -1\n",
    "\n",
    "        # get maximum number--minimum number of semesters to take all courses\n",
    "        ans = 0\n",
    "        for i in range(1,n+1):\n",
    "            ans=max(ans,dist[i])\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        record=[0 for i in range(n+1)]\n",
    "        valid=True\n",
    "        graph=[[]for i in range(n+1)]\n",
    "        res=[1 for i in range(n+1)]\n",
    "        for i,j in relations:\n",
    "            graph[j].append(i)\n",
    "\n",
    "        \n",
    "        def dfs(cur,depth):\n",
    "            nonlocal valid\n",
    "            nonlocal maxx\n",
    "            record[cur]=1\n",
    "            for fa in graph[cur]:\n",
    "                if record[fa]==0:\n",
    "                    print(maxx)\n",
    "                    maxx=max(maxx,depth+1)\n",
    "                    dfs(fa,depth+1)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif record[fa]==1:\n",
    "                    valid=False\n",
    "                    return\n",
    "                elif record[fa]==2:\n",
    "                    maxx=max(maxx,res[fa]+1)\n",
    "            record[cur]=2\n",
    "            res[cur]=maxx\n",
    "            return\n",
    "        for i in range(1,n+1):\n",
    "            if record[i]==0:\n",
    "                maxx=1\n",
    "                dfs(i,1)\n",
    "        if not valid:\n",
    "            return -1\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        adjGraph = defaultdict(set)\n",
    "        inDegrees = defaultdict(int)\n",
    "        visited = set()\n",
    "        for u,v in relations:\n",
    "            adjGraph[u].add(v)\n",
    "            inDegrees[v] += 1\n",
    "        queue = deque(node for node in range(1, n+1) if inDegrees[node] == 0)\n",
    "        season = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                visited.add(cur)\n",
    "                for neighbor in adjGraph[cur]:\n",
    "                    if neighbor not in visited:\n",
    "                        inDegrees[neighbor] -= 1\n",
    "                        if inDegrees[neighbor] == 0:\n",
    "                            queue.append(neighbor)\n",
    "            season += 1\n",
    "        return season if len(visited) == n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        mp = defaultdict(set)\n",
    "\n",
    "        for pre, after in relations:\n",
    "            mp[after].add(pre)\n",
    "\n",
    "        semester = set([i+1 for i in range(n)])\n",
    "        ans = 0\n",
    "        while semester:\n",
    "            toTake = set()\n",
    "            for e in semester:\n",
    "                if not mp[e]:\n",
    "                    toTake.add(e)\n",
    "            if not toTake:\n",
    "                return -1\n",
    "            for c in toTake:\n",
    "                semester.remove(c)\n",
    "                for tmp in mp:\n",
    "                    if c in mp[tmp]:\n",
    "                        mp[tmp].remove(c)\n",
    "            ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        mp = defaultdict(set)\n",
    "\n",
    "        for pre, after in relations:\n",
    "            mp[after].add(pre)\n",
    "\n",
    "        semester = set([i+1 for i in range(n)])\n",
    "        ans = 0\n",
    "        while semester:\n",
    "            toTake = set()\n",
    "            for e in semester:\n",
    "                if not mp[e]:\n",
    "                    toTake.add(e)\n",
    "            if not toTake:\n",
    "                return -1\n",
    "            for c in toTake:\n",
    "                semester.remove(c)\n",
    "                for tmp in mp:\n",
    "                    if c in mp[tmp]:\n",
    "                        mp[tmp].remove(c)\n",
    "            ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        pre = defaultdict(set)\n",
    "        nex = defaultdict(list)\n",
    "        f = set(range(1,n+1))\n",
    "        for p,q in relations:\n",
    "           nex[p].append(q)\n",
    "           pre[q].add(p)\n",
    "           if q in f:f.remove(q)\n",
    "        if len(f)==0:\n",
    "            return -1\n",
    "        v = set(f)\n",
    "        ne = set()\n",
    "        c = 0\n",
    "        while True:\n",
    "            c+=1\n",
    "            for i in f:\n",
    "                for j in nex[i]:\n",
    "                    if len(pre[j]-v)==0:\n",
    "                        ne.add(j)\n",
    "            if len(ne)==0:\n",
    "                return -1\n",
    "            v = v.union(ne)\n",
    "            f = ne\n",
    "            ne = set()\n",
    "            if len(v)==n:\n",
    "                return c+1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        e = defaultdict(set)\n",
    "        indeg = [0 for _ in range(n)]\n",
    "        for x,y in relations:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            e[x].add(y)\n",
    "            indeg[y] += 1\n",
    "        vis = set()\n",
    "        q = deque()\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 0:\n",
    "                vis.add(i)\n",
    "                q.append(i)\n",
    "        while True:\n",
    "            f = 0\n",
    "            ll = len(q)\n",
    "            while ll:\n",
    "                ll -= 1\n",
    "                cur = q.popleft()\n",
    "                for nxt in e[cur]:\n",
    "                    indeg[nxt] -= 1\n",
    "                    if indeg[nxt] == 0:\n",
    "                        vis.add(nxt)\n",
    "                        q.append(nxt)\n",
    "                        f = 1\n",
    "                \n",
    "            if f:\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans if len(vis) == n else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "            \n",
    "            UNVISITED, VISITING, VISITED = 0, 1, 2\n",
    "            status = [UNVISITED] * ( n + 1)\n",
    "            adjacency_list = [[] for _ in range(n + 1)]\n",
    "            has_loop = False\n",
    "            # depth = [1] * (n + 1) # 记录每个节点最大call stack深度\n",
    "            depth = 0\n",
    "\n",
    "            @lru_cache(None)\n",
    "            def dfs(node):\n",
    "                nonlocal has_loop\n",
    "                if has_loop: return -1\n",
    "                if status[node] == VISITING:\n",
    "                # 回到正在搜索的节点说明有环\n",
    "                    has_loop = True\n",
    "                    return -1\n",
    "                # if status[node] == VISITED:\n",
    "                # # 遇到已经搜索完成的节点可以返回了，该节点已在栈中，不返回的话就死循环了\n",
    "                #     return  \n",
    "                # 只对没有访问过的节点开始搜索\n",
    "                status[node] = VISITING # 在入栈前先标记\n",
    "                tdepth = 0\n",
    "                for neighbor in adjacency_list[node]:\n",
    "                    tdepth = max(dfs(neighbor), tdepth)\n",
    "                status[node] = VISITED # 出栈返回后标记已访问\n",
    "                return tdepth + 1\n",
    "            \n",
    "            for course, prerequisite in relations:\n",
    "                adjacency_list[prerequisite].append(course)\n",
    "\n",
    "            for course in range(1, n + 1):\n",
    "                if status[course] == UNVISITED:\n",
    "                    ans = dfs(course)\n",
    "                    if has_loop: return - 1\n",
    "                    else:\n",
    "                        depth = max(depth, ans)\n",
    "                    \n",
    "            return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        hashmap = defaultdict(set)\n",
    "        to = defaultdict(set)\n",
    "        all = set()\n",
    "        for a, b in relations:\n",
    "            hashmap[b].add(a)\n",
    "            to[a].add(b)\n",
    "            all.add(a)\n",
    "            all.add(b)\n",
    "        stack = [k for k in all if not len(hashmap[k])]\n",
    "        hashmap = {k: len(v) for k, v in hashmap.items() if len(v)}\n",
    "        ans = 0\n",
    "        while stack:\n",
    "            ans += 1\n",
    "            ref = []\n",
    "            for node in stack:\n",
    "                for next in to[node]:\n",
    "                    hashmap[next] -= 1\n",
    "                    if hashmap[next] == 0:\n",
    "                        ref.append(next)\n",
    "                        del hashmap[next]\n",
    "            stack = ref\n",
    "        return ans if len(hashmap) == 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "            \n",
    "            UNVISITED, VISITING, VISITED = 0, 1, 2\n",
    "            status = [UNVISITED] * ( n + 1)\n",
    "            adjacency_list = [[] for _ in range(n + 1)]\n",
    "            has_loop = False\n",
    "            max_depth = 0\n",
    "\n",
    "            @lru_cache(None)\n",
    "            def dfs(node): \n",
    "                nonlocal has_loop\n",
    "                if has_loop: return -1 # 必须返回一个数字否则后面取max会报错\n",
    "                if status[node] == VISITING:\n",
    "                    has_loop = True\n",
    "                    return -1\n",
    "\n",
    "                status[node] = VISITING # 在入栈前先标记\n",
    "                depth = 0 \n",
    "                for neighbor in adjacency_list[node]:\n",
    "                    depth = max(dfs(neighbor), depth)\n",
    "                status[node] = VISITED # 出栈返回后标记已访问\n",
    "                return depth + 1\n",
    "            \n",
    "            for course, prerequisite in relations:\n",
    "                adjacency_list[prerequisite].append(course)\n",
    "\n",
    "            for course in range(1, n + 1):\n",
    "                if status[course] == UNVISITED:\n",
    "                    depth = dfs(course)\n",
    "                    if has_loop: return - 1\n",
    "                    else:\n",
    "                        max_depth = max(max_depth, depth)\n",
    "                    \n",
    "            return max_depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        #we can tranverse thru the graph find the highest depth from the root to leaf\n",
    "        graph = [[] for _ in range(n)]\n",
    "        self.dp = [-1 for _ in range(n)]\n",
    "        vis = [-1 for _ in range(n)]\n",
    "        \n",
    "        for edge in relations:\n",
    "            graph[edge[0] - 1].append(edge[1] - 1)\n",
    "        self.cyc = False\n",
    "        def dfs(cur):\n",
    "            if self.dp[cur] == 0:\n",
    "                self.cyc = True\n",
    "                return -1\n",
    "\n",
    "            if not graph[cur]:\n",
    "                self.dp[cur] = 1\n",
    "                return 1\n",
    "            if self.dp[cur] > 0:\n",
    "                return self.dp[cur]\n",
    "            res = 0\n",
    "            self.dp[cur] = 0\n",
    "            for i in graph[cur]:\n",
    "                res = max(res , dfs(i))\n",
    "            self.dp[cur] = res + 1\n",
    "            return res + 1\n",
    "\n",
    "\n",
    "        sem_cnt = 0\n",
    "        for i in range(n):\n",
    "            sem_cnt = max(sem_cnt , dfs(i))\n",
    "        \n",
    "        #print(self.dp)\n",
    "        if self.cyc: return -1\n",
    "        return sem_cnt \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        def dfs(course,depth):\n",
    "            if visited[course] == 1: return True\n",
    "            if visited[course] == -1 and depth < depths[course]: return False\n",
    "            if adjMatrix[course] == []:\n",
    "                depths[course] = depth+1\n",
    "                self.res = max(self.res,depth+1)\n",
    "                return False\n",
    "            visited[course] = 1\n",
    "            for c in adjMatrix[course]:\n",
    "                if dfs(c,depth+1):\n",
    "                    return True\n",
    "            visited[course] = -1\n",
    "            depths[course] = depth+1\n",
    "            return False\n",
    "\n",
    "        adjMatrix = [[] for _ in range(n)]\n",
    "        for pre,post in relations:\n",
    "            adjMatrix[pre-1].append(post-1)\n",
    "\n",
    "        visited = [0] * n\n",
    "        depths = [0] * n\n",
    "        self.res = 0\n",
    "        for course in range(n):\n",
    "            if dfs(course,0):\n",
    "                return -1\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "            \n",
    "            UNVISITED, VISITING, VISITED = 0, 1, 2\n",
    "            status = [UNVISITED] * ( n + 1)\n",
    "            adjacency_list = [[] for _ in range(n + 1)]\n",
    "            has_loop = False\n",
    "            depth = [1] * (n + 1) # 记录每个节点最大call stack深度\n",
    "             \n",
    "            @lru_cache(None)\n",
    "            def dfs(node):\n",
    "                nonlocal has_loop\n",
    "                if has_loop: return\n",
    "                if status[node] == VISITING:\n",
    "                # 回到正在搜索的节点说明有环\n",
    "                    has_loop = True\n",
    "                    return \n",
    "                if status[node] == VISITED:\n",
    "                # 遇到已经搜索完成的节点可以返回了，该节点已在栈中，不返回的话就死循环了\n",
    "                    return  \n",
    "                # 只对没有访问过的节点开始搜索\n",
    "                status[node] = VISITING # 在入栈前先标记\n",
    "                for neighbor in adjacency_list[node]:\n",
    "                    dfs(neighbor)\n",
    "                    depth[node] = max(depth[node], depth[neighbor] + 1)\n",
    "                status[node] = VISITED # 出栈返回后标记已访问\n",
    "                return \n",
    "            \n",
    "            for course, prerequisite in relations:\n",
    "                adjacency_list[prerequisite].append(course)\n",
    "\n",
    "            for course in range(1, n + 1):\n",
    "                if status[course] == UNVISITED:\n",
    "                    dfs(course)\n",
    "                    if has_loop: return -1\n",
    "                    \n",
    "            return max(depth) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        hashmap = defaultdict(set)\n",
    "        to = defaultdict(set)\n",
    "        all = set()\n",
    "        for a, b in relations:\n",
    "            hashmap[b].add(a)\n",
    "            to[a].add(b)\n",
    "            all.add(a)\n",
    "            all.add(b)\n",
    "        reff = ans = 0\n",
    "        dp = {}\n",
    "        stack = []\n",
    "        for k in all:\n",
    "            if not len(hashmap[k]):\n",
    "                stack.append(k)\n",
    "            dp[k] = len(hashmap[k])\n",
    "        while stack:\n",
    "            reff += len(stack)\n",
    "            ans += 1\n",
    "            ref = []\n",
    "            for node in stack:\n",
    "                for next in to[node]:\n",
    "                    dp[next] -= 1\n",
    "                    if dp[next] == 0:\n",
    "                        ref.append(next)\n",
    "            stack = ref\n",
    "        return ans if reff == len(all) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        def dfs(course,depth):\n",
    "            if visited[course] == 1: return True\n",
    "            if visited[course] == -1 and depth < depths[course]: return False\n",
    "            if adjMatrix[course] == []:\n",
    "                depths[course] = depth+1\n",
    "                self.res = max(self.res,depth+1)\n",
    "                return False\n",
    "            visited[course] = 1\n",
    "            for c in adjMatrix[course]:\n",
    "                if dfs(c,depth+1):\n",
    "                    return True\n",
    "            visited[course] = -1\n",
    "            depths[course] = depth+1\n",
    "            return False\n",
    "\n",
    "        adjMatrix = [[] for _ in range(n)]\n",
    "        for pre,post in relations:\n",
    "            adjMatrix[pre-1].append(post-1)\n",
    "\n",
    "        visited = [0] * n\n",
    "        depths = [0] * n\n",
    "        self.res = 0\n",
    "        for course in range(n):\n",
    "            if dfs(course,0):\n",
    "                return -1\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        # 1、不管怎样还是要先构图\n",
    "        g = [[] for _ in range(n)]\n",
    "        ind = [0 for _ in range(n)]\n",
    "        for u, v in relations:\n",
    "            g[u-1].append(v-1)\n",
    "            ind[v-1] += 1\n",
    "        \n",
    "        # 2、跑一下环检测，判断无法实现的情况\n",
    "        has_cycle = False\n",
    "        vis = [False for _ in range(n)]\n",
    "        def dfs(node, path):\n",
    "            nonlocal has_cycle\n",
    "            if path >> node & 1:\n",
    "                has_cycle = True\n",
    "                return\n",
    "            if vis[node] or has_cycle:\n",
    "                return \n",
    "            vis[node] = True\n",
    "            for s in g[node]:\n",
    "                    dfs(s, path | 1 << node)\n",
    "                    \n",
    "        for i in range(n):\n",
    "            dfs(i, 0)\n",
    "        if has_cycle:\n",
    "            return -1\n",
    "        \n",
    "        # 3、跑一下bfs最长路就完事了\n",
    "        cur = [i for i in range(n) if ind[i] == 0]\n",
    "        step = 0\n",
    "        while cur:\n",
    "            step += 1\n",
    "            nxt = set()\n",
    "            for node in cur:\n",
    "                for s in g[node]:\n",
    "                    ind[s] -= 1\n",
    "                    if ind[s] == 0:\n",
    "                        nxt.add(s)\n",
    "            cur = list(nxt)\n",
    "        \n",
    "        return step\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        def dfs(course,depth):\n",
    "            if visited[course] == 1: return True\n",
    "            if visited[course] == -1 and depth < depths[course]: return False\n",
    "            if adjMatrix[course] == []:\n",
    "                depths[course] = depth+1\n",
    "                self.res = max(self.res,depth+1)\n",
    "                return False\n",
    "            visited[course] = 1\n",
    "            for c in adjMatrix[course]:\n",
    "                if dfs(c,depth+1):\n",
    "                    return True\n",
    "            visited[course] = -1\n",
    "            depths[course] = depth+1\n",
    "            return False\n",
    "\n",
    "        adjMatrix = [[] for _ in range(n)]\n",
    "        for pre,post in relations:\n",
    "            adjMatrix[pre-1].append(post-1)\n",
    "\n",
    "        visited = [0] * n\n",
    "        depths = [0] * n\n",
    "        self.res = 0\n",
    "        for course in range(n):\n",
    "            if dfs(course,0):\n",
    "                return -1\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        edges=collections.defaultdict(list)\n",
    "\n",
    "        for info in relations:\n",
    "            edges[info[1]-1].append(info[0]-1)\n",
    "\n",
    "        print(edges)\n",
    "        visited = [0]*n\n",
    "        visited_length = [0]*n        \n",
    "\n",
    "        valid = 1\n",
    "\n",
    "        def dfs(i):\n",
    "            visited[i]=1\n",
    "\n",
    "            nonlocal valid\n",
    "            \n",
    "            max_len = 0\n",
    "            for j in edges[i]:\n",
    "                if not visited[j]:\n",
    "                    dfs(j)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif visited[j]==1:\n",
    "                    valid = False\n",
    "                    return\n",
    "                max_len = max(max_len, visited_length[j])\n",
    "            \n",
    "            visited[i]=2\n",
    "            visited_length[i]=1+max_len\n",
    "\n",
    "            pass\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            if not visited[i] and valid:\n",
    "                dfs(i)\n",
    "        print(visited_length)\n",
    "        return max(visited_length) if valid else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        graph = {i:[] for i in range(1,n+1)}\n",
    "        for u,v in relations:\n",
    "            graph[u].append(v)\n",
    "\n",
    "        visited = {}\n",
    "\n",
    "        # 判断是否有环\n",
    "        def dfs(node:int) -> int:\n",
    "            if node not in visited:\n",
    "                # 表示正在访问\n",
    "                visited[node] = -1\n",
    "            else:\n",
    "                # 返回最长路径\n",
    "                return visited[node]\n",
    "\n",
    "            max_length = 1\n",
    "            for v in graph[node]:\n",
    "                length = dfs(v)\n",
    "                if length == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    max_length = max(length+1,max_length)\n",
    "            visited[node] = max_length\n",
    "            return max_length\n",
    "\n",
    "        max_length = -1\n",
    "        for node in graph.keys():\n",
    "            length = dfs(node)\n",
    "            if length == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                max_length = max(max_length,length)\n",
    "        return max_length\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(1, N + 1)}\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "\n",
    "        visited = {}\n",
    "\n",
    "        def dfs(node: int) -> int:\n",
    "            # 返回最长路（含）\n",
    "            if node in visited:\n",
    "                return visited[node]\n",
    "            else:\n",
    "                # 标记为正在访问\n",
    "                visited[node] = -1\n",
    "\n",
    "            max_length = 1\n",
    "            for end_node in graph[node]:\n",
    "                length = dfs(end_node)\n",
    "                # 我们遇到了一个环！\n",
    "                if length == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    max_length = max(length+1, max_length)\n",
    "            # 标记为已经访问过\n",
    "            visited[node] = max_length\n",
    "            return max_length\n",
    "\n",
    "        max_length = -1\n",
    "        for node in graph.keys():\n",
    "            length = dfs(node)\n",
    "            # 我们遇到了一个环！\n",
    "            if length == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                max_length = max(length, max_length)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        #graph = {i: [] for i in range(1, N + 1)}\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "        print(graph)\n",
    "\n",
    "        visited = {}\n",
    "\n",
    "        def dfs(node: int) -> int:\n",
    "            # 返回最长路（含）\n",
    "            if node in visited:\n",
    "                return visited[node]\n",
    "            else:\n",
    "                # 标记为正在访问\n",
    "                visited[node] = -1\n",
    "\n",
    "            max_length = 1\n",
    "            for end_node in graph[node]:\n",
    "                length = dfs(end_node)\n",
    "                # 我们遇到了一个环！\n",
    "                if length == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    max_length = max(length+1, max_length)\n",
    "            # 标记为已经访问过\n",
    "            visited[node] = max_length\n",
    "            return max_length\n",
    "\n",
    "        max_length = -1\n",
    "        for node in list(graph.keys()):\n",
    "            length = dfs(node)\n",
    "            # 我们遇到了一个环！\n",
    "            if length == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                max_length = max(length, max_length)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        #graph = {i: [] for i in range(1, N + 1)} #列表推导式生成的字典key长度固定的 所以可以使用 for node in graph.keys():\n",
    "        #如果是在for循环中 逐渐生成的字典直接使用 上述循环会报错 需要把迭代器转换成列表 for node in list(graph.keys()):\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "        print(graph)\n",
    "\n",
    "        visited = {}\n",
    "\n",
    "        def dfs(node: int) -> int:\n",
    "            # 返回最长路（含）\n",
    "            if node in visited:\n",
    "                return visited[node]\n",
    "            else:\n",
    "                # 标记为正在访问\n",
    "                visited[node] = -1\n",
    "\n",
    "            max_length = 1\n",
    "            for end_node in graph[node]:\n",
    "                length = dfs(end_node)\n",
    "                # 我们遇到了一个环！\n",
    "                if length == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    max_length = max(length+1, max_length)\n",
    "            # 标记为已经访问过\n",
    "            visited[node] = max_length\n",
    "            return max_length\n",
    "\n",
    "        max_length = -1\n",
    "        for node in list(graph.keys()):\n",
    "            length = dfs(node)\n",
    "            # 我们遇到了一个环！\n",
    "            if length == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                max_length = max(length, max_length)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(1, N + 1)}\n",
    "        for start_node, end_node in relations:\n",
    "            graph[start_node].append(end_node)\n",
    "\n",
    "        visited = {}\n",
    "\n",
    "        def dfs(node: int) -> int:\n",
    "            # 返回最长路（含）\n",
    "            if node in visited:\n",
    "                return visited[node]\n",
    "            else:\n",
    "                # 标记为正在访问\n",
    "                visited[node] = -1\n",
    "\n",
    "            max_length = 1\n",
    "            for end_node in graph[node]:\n",
    "                length = dfs(end_node)\n",
    "                # 我们遇到了一个环！\n",
    "                if length == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    max_length = max(length+1, max_length)\n",
    "            # 标记为已经访问过\n",
    "            visited[node] = max_length\n",
    "            return max_length\n",
    "\n",
    "        max_length = -1\n",
    "        for node in graph.keys():\n",
    "            length = dfs(node)\n",
    "            # 我们遇到了一个环！\n",
    "            if length == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                max_length = max(length, max_length)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:\n",
    "        # 找最大深度\n",
    "        # 广度优先搜索，实现层序遍历\n",
    "        # 染色\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for pre, nxt in relations:\n",
    "            graph[pre].append(nxt)\n",
    "        \n",
    "        visited = {}\n",
    "        \n",
    "        def dfs_check_cycle(u: int):\n",
    "            if u in visited:\n",
    "                return visited[u]\n",
    "            else:\n",
    "                visited[u] = -1\n",
    "            for v in graph[u]:\n",
    "                if dfs_check_cycle(v):\n",
    "                    return True\n",
    "            visited[u] = False\n",
    "            return False\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            if dfs_check_cycle(i):\n",
    "                return -1\n",
    "        \n",
    "        depth = [0] * (n + 1)\n",
    "        \n",
    "        def dfs_get_max_depth(u: int) -> int:\n",
    "            if depth[u]:\n",
    "                return depth[u]\n",
    "            depth[u] = 1  # 初始化节点的深度\n",
    "            for v in graph[u]:\n",
    "                depth[u] = max(dfs_get_max_depth(v) + 1, depth[u])\n",
    "                \n",
    "            return depth[u]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            dfs_get_max_depth(i)\n",
    "\n",
    "        return max(depth)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
